package com.elloe.实现二叉树的Node节点.数组升华二叉树;

import com.elloe.实现二叉树的Node节点.Node的Java实现.Node;

import java.util.List;

/**
 * @author ElloeStudy(Sifa Zhang)
 * @create 2022-04-09 13:18
 * To: 真常应物，真常得性，常清常静，常清静矣
 *
 * 数组变二叉树
 */
public class BinaryFromArray {
    public static void create(int[] datas, List<Node> list){
        // 将数组的数装换为节点Node
        for (int i = 0; i < datas.length; i++) {
            Node node = new Node(datas[i]);
            node.setNode(node);
            list.add(node);
        }
        
        // 节点关联树
        for (int index = 0; index < list.size()/2 - 1; index++) {
            //编号为n的节点他的左子节点编号为2*n 右子节点编号为2*n+1 但是因为list从0开始编号，所以还要+1
            list.get(index).setLeft(list.get(index * 2 + 1));
            list.get(index).setRight(list.get(index * 2 + 2));
        }

        // 单独处理最后一个节点，list.size()/2 -1 进行设置，避免单孩子情况
        int index = list.size()/2 - 1;
        list.get(index).setLeft(list.get(index * 2 + 1));
        if (list.size()%2 == 1){
            // 如果有奇数个节点，最后一个节点才有右节点
            list.get(index).setRight(list.get(index * 2 + 2));
        }
    }
}
